package tree.traverse;

import java.util.ArrayList;
import java.util.List;

/**
 * 树遍历基础版本
 * Definition for a binary tree node.
 * public class TreeNode {
 * int val;
 * TreeNode left;
 * TreeNode right;
 * TreeNode() {}
 * TreeNode(int val) { this.val = val; }
 * TreeNode(int val, TreeNode left, TreeNode right) {
 * this.val = val;
 * this.left = left;
 * this.right = right;
 * }
 * }
 */
public class BasicTreeOrder {

    public static void main(String[] args) {

        //1,2,3,null,null,4,5
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        treeNode.right = new TreeNode(3);
        treeNode.right.left = new TreeNode(4);
        treeNode.right.right = new TreeNode(5);

        BasicTreeOrder bt = new BasicTreeOrder();
        System.out.println("前序遍历： " + bt.preOrderTraversal(treeNode));
        System.out.println("中序遍历： " + bt.inOrderTraversal(treeNode));
        System.out.println("后序遍历： " + bt.postOrderTraversal(treeNode));
    }


    public List<Integer> preOrderTraversal(TreeNode root) {

        if (root == null) {
            return null;
        }

        List<Integer> ret = new ArrayList<Integer>();
        List<Integer> left = preOrderTraversal(root.left);
        List<Integer> right = preOrderTraversal(root.right);

        //不同的顺序，决定不同的遍历； 根的遍历顺序
        // 前序遍历：根前，从左到右
        // 中序遍历：根中，从左到右
        // 后序遍历：根后，从左到右
        ret.add(root.val);
        if (left != null) {
            ret.addAll(left);
        }
        if (right != null) {
            ret.addAll(right);
        }

        return ret;
    }

    public List<Integer> inOrderTraversal(TreeNode root) {

        if (root == null) {
            return null;
        }
        List<Integer> ret = new ArrayList<Integer>();
        List<Integer> left = inOrderTraversal(root.left);
        List<Integer> right = inOrderTraversal(root.right);

        //不同的顺序，决定不同的遍历； 根的遍历顺序
        // 前序遍历：根前，从左到右
        // 中序遍历：根中，从左到右
        // 后序遍历：根后，从左到右
        if (left != null) {
            ret.addAll(left);
        }
        ret.add(root.val);
        if (right != null) {
            ret.addAll(right);
        }

        return ret;
    }

    public List<Integer> postOrderTraversal(TreeNode root) {

        if (root == null) {
            return null;
        }
        List<Integer> ret = new ArrayList<Integer>();
        List<Integer> left = postOrderTraversal(root.left);
        List<Integer> right = postOrderTraversal(root.right);

        //不同的顺序，决定不同的遍历； 根的遍历顺序
        // 前序遍历：根前，从左到右
        // 中序遍历：根中，从左到右
        // 后序遍历：根后，从左到右
        if (left != null) {
            ret.addAll(left);
        }
        if (right != null) {
            ret.addAll(right);
        }
        ret.add(root.val);

        return ret;
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int val) {
        this.val = val;
    }
}